Binary Search Tips

Binary Search is one of the most common techniques being used in scenarios of searching. It has many types of variants and I would like to discuss some of it and why the edge cases are designed like this.

1.Search for a element in array (familiar)

This is probably the most common way to use binary search. It involves finding mid point within a range and thus divides the range (smaller the search range) based on the midpoint. Common implementation is:

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // key criterion 

    while(left <= right) { // key criteria
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid; // key criterion, directly return
        else if (nums[mid] < target)
            left = mid + 1; // key criterion
        else if (nums[mid] > target)
            right = mid - 1; // key criterion
    }
    return -1;
}

Some important value includes: value of initial right, different value assignment in three different cases (less than, larger than, or equal to), and the criterion of while loop (< or <= ?).

1. value of right: By assigning “nums.length - 1”, we means that we are searching in range [left, right] (right boundary inclusive).If “nums.length”, then we are saying [left, right) (right boundary inclusive)

2. while loop criterion (< or <=) : By assigning <, we should jump out of the loop when left == right, which means that [left, right] will results in a omitted value, and [left, right) will not omit. Therefore when we pick the criterion, we should adjust the initial value of right accordingly to avoid unexpected behavior.

In short: (right = nums.length - 1, then while <=), (right = nums.length, then while <)

3. Different cases for <, > , ==: The value assignment for different case really depends on what you would like to find

   1. Find index of a element (value may have duplicate, so random occurrence): < : left = mid + 1, >:right = mid - 1, == : return mid;

   2. Find index of the left boundary (first occurrence) of a element:

   < : left = mid + 1, >:right = mid - 1, == : right = mid - 1 (narrow the right boundary to finally get the left bound);

   3. Find index of the right boundary (last occurrence) of a element:

   < : left = mid + 1, >:right = mid - 1, == : left = mid + 1 (narrow the left boundary to finally get the right bound);

2.Search for boundary in a array (first or last occurrence)

When find left bound or right bound, be careful of indexOutBoundary error when the target element is bigger/smaller than all elements in array. In that case, right value will be left - 1/left value be right +1. For example, when we end up with range such as [9(left), 8(right)], apparently, it is not reasonable to take left bound 9 as our final left bound since the range contain no value. So, make sure we check for rationality at the end.

// Finally, after while loop, check Out of Boundary error
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;

To Wrap this up, we have three different implementation template for finding index, first occurrence (left bound) ,and last occurrence(right bound) as follows:

// To keep consistency, we use nums.length - 1 for right, and <= criterion in while loop
int binary_search(int[] nums, int target) {
    int left = 0, right = nums.length - 1; 
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            // directly return
            return mid;
        }
    }
 	
    return -1;
}

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // No return, keep narrowing the right bound
            right = mid - 1;
        }
    }
    // check left bound rationality
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}


int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // No return, keep narrowing the left bound
            left = mid + 1;
        }
    }
    // check right bound rationality
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}

Besides my provided templates, there are many different implementations, some embedded condition checked edition are like:

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    
    // new variable to record final result
    int res = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // No return, keep narrowing the right bound
            right = mid - 1;
        }
        
        // New operation to record 
        if(nums[mid] == target) {
            res = mid;
        }
    }
    
    return res;
}

int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;

    // new variable to record final result
    int res = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // No return, keep narrowing the left bound
            left = mid + 1;
        }
        
        // New operation to record 
        if(nums[mid] == target) {
            res = mid;
        }
    }
    
    
    return res;
}

• 本文作者： Yu Wan
• 本文链接： https://cyanh1ll.github.io/2021/01/11/Binary Search tips/
• 版权声明： CYANH1LL